//
// Description: 24. 两两交换链表中的节点
// Created by Loading on 2022/5/2.
//

#include <bits/stdc++.h>
#include <Data_Structure_Definition.h>
#include <Utils.h>

using namespace std;

/* 递归 */
ListNode *swapPairs_Recursion(ListNode *head) {
    if (!head || !head->next) {
        return head;
    }
    // 新的头
    auto newHead = head->next;
    head->next = swapPairs_Recursion(newHead->next);
    newHead->next = head;

    return newHead;
}

/* 迭代 */
ListNode *swapPairs(ListNode *head) {
    // 辅助头结点
    auto hair = new ListNode(-1);
    hair->next = head;
    // 前驱节点，方便连接交换后的节点
    auto pre = hair;
    while (head && head->next) {
        // 交换
        auto tail = head->next;
        pre->next = tail;
        head->next = tail->next;
        tail->next = head;
        // 更新前驱节点和要交换的第一个节点
        pre = head;
        head = head->next;
    }

    auto res = hair->next;
    // 防止内存泄漏
    delete hair;

    return res;
}

int main() {
    vector<int> nums{1, 2, 3, 4, 5};
    // 迭代
    auto head = generateListNode(nums);
    auto res = swapPairs(head);
    cout << printfListNode(res) << endl;
    // 递归
    head = generateListNode(nums);
    res = swapPairs_Recursion(head);
    cout << printfListNode(res) << endl;

    return 0;
}